﻿// Write a program that finds the index of given element in a sorted array of integers by using the binary search algorithm 
// (find it in Wikipedia).

using System;

class BinarySearch
{
    static void Main()
    {
        // get the length of the array
        Console.Write("Enter length of the array : ");
        string length = Console.ReadLine();
        int lengthOfArray;
        while (!int.TryParse(length, out lengthOfArray))
        {
            Console.Write("Invalid input. Enter again length for the array : ");
            length = Console.ReadLine();
        }

        // get the wanted element
        Console.Write("Enter the wanted element : ");
        string elementStr = Console.ReadLine();
        int wantedElement;
        while (!int.TryParse(elementStr, out wantedElement))
        {
            Console.Write("Invalid input. Enter again the wanted sum : ");
            elementStr = Console.ReadLine();
        }


        if (lengthOfArray < 0)
        {
            Console.WriteLine("Invalid input. The length should be bigger than 0. Start the program again.");
        }
        else
        {

            int[] array = new int[lengthOfArray];

            for (int index = 0; index < lengthOfArray; index++)
            {
                // get the element of the array
                Console.Write("Enter element of the array : ");
                string element = Console.ReadLine();
                int elementOfArray;
                while (!int.TryParse(element, out elementOfArray))
                {
                    Console.Write("Invalid input. Enter element again : ");
                    element = Console.ReadLine();
                }
                array[index] = elementOfArray;
            }

            Array.Sort(array); // sort the array just in case

            int startIndex = 0;
            int endIndex = lengthOfArray - 1;
            int searchedIndex = -1;

            while (endIndex >= startIndex)
            {
                int centerIndex = (startIndex + endIndex) / 2;

                if (array[centerIndex] < wantedElement)
                {
                    startIndex = centerIndex + 1;
                }
                else if (array[centerIndex] > wantedElement)
                {
                    endIndex = centerIndex - 1;
                }
                else
                {
                    searchedIndex = centerIndex;
                    break;
                }
            }

            // display the result
            if (searchedIndex == -1)
            {
                Console.WriteLine("The searched element does not exist in this array.");
            }
            else
            {
                Console.WriteLine("The searched index is : " + searchedIndex);
            }
        }
    }
}
